<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>22. 括号生成</title>
</head>
<body>
    <script>
//         数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

 

// 示例 1：

// 输入：n = 3
// 输出：["((()))","(()())","(())()","()(())","()()()"]
// 示例 2：

// 输入：n = 1
// 输出：["()"]
 

// 提示：

// 1 <= n <= 8
/**
 * @param {number} n
 * @return {string[]}
 */
 var generateParenthesis = function(n) {
    const result = []; // 初始化结果数组，用于存放所有有效的括号组合

    // 定义回溯函数，用于递归构建括号字符串
    function backtrack(currentStr, open, close) {
        // 如果当前字符串的长度等于2*n，则表示一个有效的括号序列已经生成
        if (currentStr.length === 2 * n) {
            result.push(currentStr); // 将当前字符串添加到结果数组中
            return; // 结束当前递归分支
        }

        // 如果左括号的数量小于n，则可以添加左括号
        if (open < n) {
            backtrack(currentStr + '(', open + 1, close); // 添加左括号，并递归调用回溯函数
        }

        // 如果右括号的数量小于左括号的数量，则可以添加右括号
        // 这保证了在任何时候，字符串中的右括号数量都不会超过左括号数量
        if (close < open) {
            backtrack(currentStr + ')', open, close + 1); // 添加右括号，并递归调用回溯函数
        }
    }

    // 从空字符串开始回溯，初始左括号和右括号数量都为0
    backtrack('', 0, 0);
    return result; // 返回最终的结果数组
};
    </script>
</body>
</html>